package com.jsy.common.leetcode;

import javax.security.auth.callback.CallbackHandler;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长
 * 子串
 *  的长度。
 */
public class Solution {
    public static void main(String[] args) {
//        jump(new int[]{2,3,1,1,4});
//        hIndex2(new int[]{1});
//        int[] ints = productExceptSelf(new int[]{1, 2, 3, 4});
//        int num = canCompleteCircuit(new int[]{1, 2, 3, 4,5}, new int[]{3, 4, 5, 1,2});
//        int num = canCompleteCircuit(new int[]{3, 4, 5}, new int[]{1, 2, 3});
//        int num = canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3});
//        int num = canCompleteCircuit(new int[]{1, 1, 1}, new int[]{1, 1, 1});

//        int num = canCompleteCircuit(new int[]{1,2,3,4,5}, new int[]{3,4,5,1,2});
//        System.out.println(num);
//        int sum = candy(new int[]{1,3,2,2,1});
//        int sum = candy(new int[]{1,3,4,5,2});
//        int sum = candy(new int[]{1,2,87,87,87,2,1});
//        int sum = candy(new int[]{1,2,4,4,4,3});
//        int sum = candy(new int[]{1,6,10,8,7,3,2});
//        int sum = candy(new int[]{0,1,2,3,2,1});
//        int sum = candy(new int[]{0,1,2,5,3,2,7});
//        int sum = candy(new int[]{5,10,10,10,10,10,10});
//        int sum = candy(new int[]{1,3,2,2,1});
//        int sum = candy(new int[]{1,2,4,4,4,3});
//        int sum = candy(new int[]{29,51,87,87,72,12});
//        System.out.println(sum);
//         int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
//         int[] height = {4,2,0,3,2,5};
//         int[] height = {2,0,2};
//         int[] height = {9,6,8,8,5,6,3};
//         int sum = trap(height);
//        System.out.println(sum);
//        int number = romanToInt("MCMXCIV");
//        int number = romanToInt("DCXXI");
//        String number = intToRoman(3749);
//        String number = intToRoman2(3749);
//        int number = lengthOfLastWord("luffy is still joyboy");
//        String number =longestCommonPrefix(new String[]{"flower2","flow3","flower4","flow3"});
//        String number =convert("AB",4);
//        int number = strStr("sadbutsad","sad");
//        List<String> number = fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."},16);
//        List<String> number = fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"},16);
//        List<String> number = fullJustify(new String[]{"ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"},16);
//        List<String> number = fullJustify(new String[]{"a"},1);
//        List<String> number = fullJustify(new String[]{"a","b","c","d","e"},1);
//        Boolean number = isPalindrome("A man, a plan, a canal: Panama");
//        Boolean number = isSubsequence("aaaaaa","bbaaaa");
//        Boolean number = isSubsequence("abc","ahbgdc");
//        int[] number = twoSum(new int[]{5,25,75},100);
//        int[] number = twoSum(new int[]{1,2,3,4,4,9,56,90},8);
//        int[] number = twoSum2(new int[]{1,2,3,4,4,9,56,90},8);
//        int[] number = twoSum3(new int[]{1,2,3,4,4,9,56,90},8);
//        int number = maxArea(new int[]{1,8,6,2,5,4,8,3,7});
//        int number = maxArea2(new int[]{1,8,6,2,5,4,8,3,7});
//        List<List<Integer>>number = threeSum(new int[]{-1,0,1,2,-1,-4});
//        int number = minSubArrayLen(213,new int[]{12,28,83,4,25,26,25,2,25,25,25,12});
//        int number = minSubArrayLen(7,new int[]{2,3,1,2,4,3});
//        int number = lengthOfLongestSubstring("pwwkew");
//        int number = lengthOfLongestSubstring("aabaab!bb");
//        List<Integer> number = findSubstring("barfoothefoobarman", new String[]{"foo","bar"});
//        List<Integer> number = findSubstring2("barfoothefoobarman", new String[]{"foo","bar"});
//        String number = minWindow2("barfoothefoobarman","feo");
//        char[][] chars = getChar();
//        boolean number = isValidSudoku(chars);
//          int[][] chars = {{1,2,3},{4,5,6},{7,8,9},{1,2,3},{4,5,6},{7,8,9}};
//          int[][] chars = {{1,2,3},{4,5,6},{7,8,9}};
//          int[][] chars = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
//        List<Integer> number = spiralOrder(chars);
//        rotate2(chars);
//        System.out.println(number);
//        gameOfLife(chars);
//        twoSum4(new int[]{3,2,4},6);
//        int number = longestConsecutive(new int[]{100, 4, 200, 1, 3, 2});
//        int number = longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1});
//        int number = longestConsecutive(new int[]{1,0,1,2});
//        List<String> number = summaryRanges(new int[]{-2147483648,0,2,3,4,6,8,9});
//        int[][] merge = merge(new int[][]{{1, 3}, {2, 6}, {6, 10}, {15, 18}});
//        int[][] merge = merge(new int[][]{{1, 3}});
//        int[][] merge = merge(new int[][]{{2,3}, {2, 2}, {3, 3}, {1, 3}, {5, 7}, {2, 2}, {4, 6}});
//        int[][] merge = insert(new int[][]{{1,5}, {6, 8}}, new int[]{0,9});
//        int[][] merge = insert(new int[][]{{0,2},{3,3}, {6, 11}}, new int[]{9,15});
//        int[][] merge = insert(new int[][]{{0,5},{9,12}}, new int[]{7,16});
//        int[][] merge = insert(new int[][]{{1,3},{6,9}}, new int[]{2,5});
//        int number = findMinArrowShots(new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}});
//        int number = findMinArrowShots(new int[][]{{-2147483646,-2147483645},{2147483646,2147483647}});
//        boolean number = isValid("([])");
//        String number = simplifyPath("/home/");
//        String number = simplifyPath("/home//foo/");
//        String number = simplifyPath2("/home/user/Documents/../Pictures");
//        String number = simplifyPath2("/../");
//        String number = simplifyPath("/a/./b/../../c/");
//        int number = calculate(" 2-1 + 2 ");

        ListNode head1 = new ListNode(1);
        ListNode listNode = head1;
        listNode.next = new ListNode(4);
        listNode = listNode.next;
        listNode.next = new ListNode(3);
        listNode = listNode.next;
        listNode.next = new ListNode(2);
        listNode = listNode.next;
        listNode.next = new ListNode(5);
        listNode = listNode.next;
        listNode.next = new ListNode(2);
        ListNode head2 = new ListNode(5);
//        listNode = head2;
//        listNode.next = new ListNode(3);
//        listNode = listNode.next;
//        listNode = listNode.next = new ListNode(4);
//        ListNode number = mergeTwoLists(head1,head2);
//        List<String> number = generateParenthesis(3);
//        ListNode number = swapPairs(head1);
//        ListNode number = reverseKGroup(head1,2);
//        int number = divide(-2147483647,-1);
//        ListNode number = reverseBetween(head1,1,2);
//        ListNode number = deleteDuplicates(head1);
//        ListNode number = rotateRight(head1,2);
//        ListNode number = partition(head1,3);

        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        int number = lruCache.get(2);
        System.out.println(number);
    }

    private static char[][] getChar() {
       char[][] chars =  new char[9][9];
//       chars = new char[][]{{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
//               {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
//               {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
//               {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
//               {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
//               {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
//               {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
//               {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
//               {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
//       chars = new char[][]{{'.','8','7','6','5','4','3','2','1'},{'2','.','.','.','.','.','.','.','.'},{'3','.','.','.','.','.','.','.','.'},{'4','.','.','.','.','.','.','.','.'},{'5','.','.','.','.','.','.','.','.'},{'6','.','.','.','.','.','.','.','.'},{'7','.','.','.','.','.','.','.','.'},{'8','.','.','.','.','.','.','.','.'},
//               {'9','.','.','.','.','.','.','.','.'}};
       chars = new char[][]{{'.','.','5','.','.','.','.','.','.'},{'.','.','.','8','.','.','.','3','.'},{'.','5','.','.','2','.','.','.','.'},{'.','.','.','.','.','.','.','.','.'},{'.','.','.','.','.','.','.','.','9'},{'.','.','.','.','.','.','4','.','.'},{'.','.','.','.','.','.','.','.','7'},{'.','1','.','.','.','.','.','.','.'},
               {'2','4','.','.','.','.','9','.','.'}};
      return  chars;
    }

    public boolean canJump(int[] nums) {
        boolean flag = false;
        if (nums ==null || nums.length <= 1){
            return true;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= max){
                max = Math.max(max, i + nums[i]);
                if (max >= nums.length - 1){
                    flag = true;
                    break;
                }
            }else {
                break;
            }
        }
        return flag;
    }

    public static int jump(int[] nums) {
        if (nums ==null || nums.length <= 1){
            return 0;
        }
        int max = 0;
        int step = 0;
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, i + nums[i]);
            if (i == end){
                end = max;
                step++;
            }
        }
        System.out.println(step);
        return step;
    }

    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0){
            return 0;
        }
        int h = citations.length;
        while (h > 0){
            int count = 0;
            for (int i = 0; i < citations.length; i++) {
                if (citations[i] >= h){
                    count++;
                }
            }
            if (h <= count){
                break;
            }{
                h--;
            }
        }
        return h;
    }
    public static int hIndex2(int[] citations) {
        if (citations == null || citations.length == 0){
            return 0;
        }
        Arrays.sort(citations);
        int h = 0;
        for (int i = citations.length-1; i >= 0; i--) {
            if (citations[i] > h){
                h++;
            }
        }
        System.out.println(h);
        return h;
    }

    public static int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0){
            return null;
        }
        int[] resultLeft = new int[nums.length];
        resultLeft[0] = 1;
        int[] resultRight = new int[nums.length];
        resultRight[nums.length-1] = 1;
        int[] result = new int[nums.length];
        for (int i = 1; i <nums.length; i++) {
            resultLeft[i] =  resultLeft[i-1] * nums[i-1];
        }
        for (int i = nums.length-1; i > 0; i--) {
            resultRight[i-1] =  resultRight[i] * nums[i];
            System.out.println(resultRight[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            result[i] = resultLeft[i] * resultRight[i];
        }
        return result;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0){
            return -1;
        }
        for (int i = 0; i < gas.length; i++) {
            int count = 0;
            int start = i;
            int gasSum = 0;
            int costSum = 0;
            boolean flag = true;
            while (count<= gas.length && flag){
                gasSum = gasSum + gas[start];
                costSum = costSum + cost[start];
                if (gasSum >= costSum){
                    start++;
                    if (start == gas.length){
                        start = 0;
                    }
                }else {
                    flag = false;
                    i = i+count;
                }
                count++;
            }
            if (count > gas.length && flag){
                return i;
            }
        }
        return -1;
    }

    public static int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0){
            return 0;
        }
        if (ratings.length == 1){
            return 1;
        }
        int[] leftResult = new int[ratings.length];
        leftResult[0] = 1;
        // 初始化数组，默认每个孩子至少分配到1个糖果
        for (int i = 1; i < leftResult.length; i++) {
            if (ratings[i] > ratings[i-1]){
                leftResult[i] = leftResult[i-1] + 1;
            }else{
                leftResult[i] = 1;
            }
        }
        int[] rightResult = new int[ratings.length];
        rightResult[rightResult.length-1] = 1;
        int sum = Math.max(leftResult[leftResult.length-1], rightResult[rightResult.length-1]);
        for (int i = rightResult.length-2; i >=0; i--) {
            if (ratings[i] > ratings[i+1]){
                rightResult[i] = rightResult[i+1] + 1;
            }else {
                rightResult[i] = 1;
            }
            int max = Math.max(leftResult[i], rightResult[i]);
            System.out.println(max);
            sum+= max;
        }
        return sum;
    }

    public static int trap(int[] height) {
        int area = 0;
        if (height == null || height.length <=2){
            return 0;
        }
        int[] leftMax = new int[height.length];
        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        int[] rightMax= new int[height.length];
        rightMax[height.length-1] = height[height.length-1];
        for (int i = height.length-2; i>=0; i--){
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
        for (int i = 0; i < height.length; i++){
            area += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return area;
    }

    /**
     * 接雨水双指针解法
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }

    /**
     * 罗马数字转整数
     * @param
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * @return
     */
    public static int romanToInt(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        int sum = 0;
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            flag = true;
            char c = s.charAt(i);
            if ('I' == c){
                if (i+1 < s.length()){
                    if ('V' == s.charAt(i+1)){
                        i++;
                        sum += 4;
                        flag = false;
                    }else if ('X' == s.charAt(i+1)){
                        i++;
                        sum += 9;
                        flag = false;
                    }
                }
                if (flag){
                    sum += 1;
                }
            }else if ('X' == c){
                if (i+1 < s.length()){
                    if ('L' == s.charAt(i+1)){
                        i++;
                        sum += 40;
                        flag = false;
                    }else if ('C' == s.charAt(i+1)){
                        i++;
                        sum += 90;
                        flag = false;
                    }
                }
                if (flag){
                    sum += 10;
                }
            }else if ('C' == c){
                if (i+1 < s.length()){
                   if ('D' == s.charAt(i+1)){
                       i++;
                       sum += 400;
                       flag = false;
                   }else if ('M' == s.charAt(i+1)){
                       i++;
                       sum += 900;
                       flag = false;
                   }
                }
                if (flag){
                    sum +=100;
                }
            }else if ('V' == c){
                sum += 5;
            }else if ('L' == c){
                sum += 50;
            }else if ('D' == c){
                sum += 500;
            }else if ('M' == c){
                sum += 1000;
            }
        }
        return sum;
    }


    private static String intToRoman(Integer number) {
        String roman = "";
        roman = romanChar(number, roman);
        return roman;
    }
    private static String romanChar(int number,String roman) {
        if (number >= 1000){
            int count = number / 1000;
            number = number%1000;
            for (int i = 0; i < count; i++) {
                roman = roman + "M";
            }
        }else if (number >= 900){
            number = number%900;
            roman = roman + "CM";
        }else if (number >= 500){
            number = number%500;
            roman = roman + "D";
        }else if (number >= 400){
            number = number%400;
            roman = roman + "CD";
        }else if (number >= 100){
            int count = number / 100;
            number = number%100;
            for (int i = 0; i < count; i++) {
                roman = roman + "C";
            }
        }else if (number >= 90){
            number = number%90;
            roman = roman + "XC";
        }else if (number >= 50){
            number = number%50;
            roman = roman + "L";
        }else if (number >= 40){
            number = number%40;
            roman = roman + "XL";
        }else if (number >= 10){
            int count = number / 10;
            number = number%10;
            for (int i = 0; i < count; i++) {
                roman = roman + "X";
            }
        }else if (number >= 9){
            number = number%9;
            roman = roman + "IX";
        }else if (number >= 5){
            number = number%5;
            roman = roman + "V";
        }else if (number >= 4){
            number = number%4;
            roman = roman + "IV";
        }else if (number >= 1){
            for (int i = 0; i < number; i++) {
                roman = roman + "I";
            }
            return roman;
        }else {
            return roman;
        }
        return romanChar(number,roman);
    }

    private static String intToRoman2(Integer num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        String roman = "";
        for (int i = 0; i < values.length; i++) {
            Integer key = values[i];
            if (num >= key){
                int count = num/key;
                for (int j = 0; j < count; j++) {
                    roman = roman + symbols[i];
                }
                num = num%key;
            }
        }
        return roman;
    }
    public static int lengthOfLastWord(String s) {
        int len  = 0;
//        for (int i = s.length()-1; i >=0; i--) {
//            char c = s.charAt(i);
//            if (i == s.length() -1 && c == ' '){
//                while (i >= 0 && s.charAt(i) == ' '){
//                    i--;
//                }
//                if (i >= 0){
//                    len++;
//                }
//            }else {
//                if (c == ' '){
//                    break;
//                }
//                len++;
//            }
//        }
        len = s.split(" ")[s.split(" ").length-1].length();
        return len;
    }

    public static String longestCommonPrefix(String[] strs) {
        String prefix = "";
        int minLen = Integer.MAX_VALUE;
        int length = strs.length;
        for (int i = 0; i < length; i++) {
           if (strs[i].length() < minLen){
               minLen = strs[i].length();
           }
        }
        for (int i = minLen-1; i >=0 ; i--) {
            String str = strs[0].substring(0,i+1);
            length = strs.length;
            while (length >0 && strs[length-1].startsWith(str)){
                length--;
            }
            if (length == 0){
                prefix = str;
                break;
            }
        }
        return prefix;
    }

    public static String reverseWords(String s) {
        s = s.replaceAll(" +", "");
        s = s.trim();
        String[] s1 = s.split(" ");
        int count = s1.length / 2;
        for (int i = 0; i < count; i++) {
            String temp = s1[i];
            s1[i] = s1[s1.length-1-i];
            s1[s1.length-1-i]= temp;
        }
        return String.join(" ",s1);
    }

    public static String convert(String s, int numRows) {
        if (numRows == 1 || s.length() == 1){
            return s;
        }
        String result = "";
        String[][] area = new String[numRows][(s.length()/(numRows + numRows - 2)+1)*(numRows-1)];
        for (int k = 0; k < s.length(); k++) {
            //列数
            int mod = (k+1) % (numRows + numRows - 2);
            //横坐标
            int column = (k+1) / (numRows + numRows - 2)*(numRows-1) + (mod > numRows ? mod - numRows + 1 : mod == 0 ? 0 : 1);
            //纵坐标
            int rows = mod > numRows ? numRows - (mod - numRows) : mod == 0 ? 2 : mod;
            //获取坐标放到二维数组
            area[rows-1][column-1] = s.substring(k,k+1);
        }
        for (int i = 0; i < area.length; i++) {
            for (int j = 0; j < area[i].length; j++) {
                if (area[i][j] != null){
                    result+=area[i][j];
                }
            }
        }
        return result;
    }


    public static int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(0)){
                if (haystack.substring(i).startsWith(needle)){
                    return i;
                }
            }
        }
        return -1;
//        return haystack.indexOf(needle);
    }
    public static List<String> fullJustify(String[] words, int maxWidth) {
        int currentLength = 0;
        int spaceCount = 0;
        int gapCount = 0;
        int times = 0;
        int startIndex = 0;
        int endIndex = 0;
        String resultString = "";
        //words的子数组
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            gapCount++;
            currentLength += words[i].length()+1;
            if (currentLength > maxWidth){
                currentLength--;
               if (currentLength > maxWidth){
                   currentLength -= words[i].length()+1;
                   endIndex = i-1;
               }else if (currentLength == maxWidth){
                   currentLength = maxWidth;
                   endIndex = i;
                   i++;
               }

                if (gapCount>2){
                    spaceCount =(maxWidth-currentLength)/(gapCount-2);
                    times = (maxWidth-currentLength)%(gapCount-2);
                }
                for (int j = startIndex; j <= endIndex; j++) {
                    if (j==endIndex){
                        resultString += words[j];
                    }else {
                        resultString += words[j]+" ";
                    }
                    if (j!=endIndex){
                        if (times>0){
                            resultString+=getSpace(spaceCount+1);
                            times--;
                        }else {
                            resultString+=getSpace(spaceCount);
                        }
                    }
                }
                if (resultString.length() < maxWidth){
                    resultString+=getSpace(maxWidth-resultString.length());
                }
                result.add(resultString);
                startIndex = i;
                resultString="";
                if (i<words.length){
                    currentLength = words[i].length()+1;
                }
                gapCount = 1;
                spaceCount= 0;
                times = 0;
            }
        }
        if (endIndex<words.length-1 || result.size()==0){
            resultString = words[startIndex];
            for (int i = startIndex+1; i < words.length; i++) {
                resultString += " "+words[i];
            }
            resultString+=getSpace(maxWidth-resultString.length());
            result.add(resultString);
        }
        return result;
    }
    public static String getSpace(int count) {
        String space= "";
        for (int i = 0; i < count; i++) {
            space = space+" ";
        }
        return space;
    }

    public static boolean isPalindrome(String s) {
        if (s==null){
            return false;
        }
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right){
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))){
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))){
                right--;
            }
            if (left < right){
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }

    public static boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

    public static int[] twoSum(int[] numbers, int target) {
        int first = 0;
        int two = 1;
        while (first < numbers.length && two < numbers.length){
            if (numbers[first]+numbers[two] == target){
                return new int[]{first+1,two+1};
            }else if (numbers[first]+numbers[two] > target){
                first++;
                while (first < two && numbers[first] + numbers[two] > target){
                    two--;
                    if (numbers[first] + numbers[two] == target){
                        return new int[]{first+1,two+1};
                    }
                }
            }else {
                if (two == numbers.length - 1) {
                    first++;
                    two = first;
                }
                two++;
            }
        }
        return new int[]{-1,-1};
    }

    public static int[] twoSum2(int[] numbers, int target) {
        int first = 0;
        int two = numbers.length-1;
        while (first < numbers.length && two < numbers.length){
            if (numbers[first]+numbers[two] == target){
                return new int[]{first+1,two+1};
            }else if (numbers[first]+numbers[two] > target){
                two--;
            }else {
                first++;
            }
        }
        return new int[]{-1,-1};
    }

    public static int[] twoSum3(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int low = i + 1;
            int height = numbers.length-1;
            while (low <= height){
                int mid = low + (height-low)/2;
                int sum = numbers[i]+numbers[mid];
                if (sum > target){
                    height = mid - 1;
                }else if (sum==target){
                    return new int[]{i+1,mid+1};
                }else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1,-1};
    }

    public static int maxArea(int[] height) {
        if (height== null || height.length==0 || height.length==1){
            return 0;
        }
        int maxArea = 0;
        int left = 0;
        for (int i = 0; i < height.length; i++) {
            left = i;
            for (int j = i+1; j < height.length; j++) {
                int area = Math.min(height[left],height[j])*(j-left);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }

    /**
     * 盛最多水的容器,双指针
     * @param height
     * @return
     */
    public static int maxArea2(int[] height) {
        if (height== null || height.length==0 || height.length==1){
            return 0;
        }
        int maxArea = 0;
        int left = 0;
        int right = height.length-1;
        while (left < right){
            int area = Math.min(height[left],height[right])*(right-left);
            if (area > maxArea) {
                maxArea = area;
            }
            if (height[left] < height[right]){
                left++;
            }else {
                right--;
            }
        }
        return maxArea;
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int j = i+1;
            int k = nums.length-1;
            while (j<k){
                if (nums[i]+nums[j]+nums[k] == 0){
                    List<Integer> group = new ArrayList<>();
                    group.add(nums[i]);
                    group.add(nums[j]);
                    group.add(nums[k]);
                    lists.add(group);
                    j++;
                    k--;
                    while (j<k && nums[j] == nums[j-1]){
                        j++;
                    }
                    while (j<k && nums[k] == nums[k+1] ){
                        k--;
                    }
                }else {
                    if (nums[i]+nums[j]+nums[k] < 0){
                        j++;
                    }else {
                        k--;
                    }
                }
            }
        }
        return lists;
    }

    /**
     * 滑动窗口,最小子数组
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int right = 0;
        int start = 0;
        int len = 0;
        for (int i = 0; i<nums.length ; i++) {
            sum+=nums[right];
            while (sum>=target){
                if (len==0){
                    len = right-start+1;
                }else {
                    len = Math.min(right-start+1,len);
                }
                sum-=nums[start];
                start++;
            }
            right++;
        }
        return len;
    }

    public static int lengthOfLongestSubstring(String s) {
        int right = 0;
        int maxLen = 0;
        int left = 0;
        Set<Character> existMAp = new HashSet<>();
        while (right < s.length()){
            while(existMAp.contains(s.charAt(right))){
                existMAp.remove(s.charAt(left));
                left++;
            }
            existMAp.add(s.charAt(right));
            right++;
            maxLen = Math.max(maxLen,existMAp.size());
        }
        return maxLen;
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        long l = System.currentTimeMillis();
        List<Integer> list = new ArrayList<>();
        if (words == null || words.length == 0){
            return list;
        }
        int wordNum = words.length;
        int wordLen = words[0].length();
        int len = wordNum*wordLen;
        if (s.length()<len){
            return list;
        }
        int start = 0;
        int end = len;
        Set<Integer> selectedSet = new HashSet<>();
        while (end<=s.length()){
            String substring = s.substring(start, end);
            for (int i = 0; i < substring.length(); i = i+wordLen) {
                String word = substring.substring(i,i+wordLen);
                for (int j = 0; j < words.length; j++) {
                    if (word.equals(words[j]) && !selectedSet.contains(j)){
                        selectedSet.add(j);
                        break;
                    }
                }
            }
            if (selectedSet.size()==wordNum){
                System.out.println(substring);
                list.add(start);
            }
            selectedSet.clear();
            start++;
            end++;
        }
        System.out.println(System.currentTimeMillis()-l);
        return list;
    }

    /**
     * 滑动窗口,串联所有单词的子串
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int length = s.length();
        int wordLength = words[0].length();
        int wordNum = words.length;
        for (int i = 0; i < wordLength; i++) {
            if (i+wordNum*wordLength>length){
                break;
            }
            Map<String, Integer> wordCountMap = new HashMap<>();
            for (int j = 0; j < wordNum; j++) {
                String word = s.substring(i+j*wordLength, i+(j+1)*wordLength);
                wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1);
            }
            for (int j = 0; j < wordNum; j++) {
                String word = words[j];
                wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) - 1);
                if (wordCountMap.get(word) == 0){
                    wordCountMap.remove(word);
                }
            }
            for (int start = i; start < length-wordNum * wordLength + 1; start = start+wordLength) {
                if (start!=i){
                    String word = s.substring(start + (wordNum-1) * wordLength, start + wordNum * wordLength);
                    wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1);
                    if (wordCountMap.get(word) == 0){
                        wordCountMap.remove(word);
                    }
                    String lastWord = s.substring(start-wordLength,start);
                    wordCountMap.put(lastWord, wordCountMap.getOrDefault(lastWord,  0) - 1);
                    if (wordCountMap.get(lastWord) == 0){
                        wordCountMap.remove(lastWord);
                    }
                }
                if (wordCountMap.isEmpty()){
                    list.add(start);
                }
            }
        }
        return list;
    }

    public static String minWindow(String s, String t) {
        String result = "";
        Map<Character, Integer> differMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
           differMap.put(t.charAt(i), differMap.getOrDefault(t.charAt(i), 0)+1);
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
           left = i;
           right = i;
           Map<Character, Integer> wordMap = new HashMap<>(differMap);
           while (right<s.length()){
               if (wordMap.containsKey(s.charAt(right))){
                   wordMap.put(s.charAt(right), wordMap.get(s.charAt(right))-1);
                   if (wordMap.get(s.charAt(right))==0){
                       wordMap.remove(s.charAt(right));
                   }
               }
               if (wordMap.isEmpty()){
                   if (result.length()==0 || right-left+1<result.length()){
                       result = s.substring(left, right+1);
                   }
                   break;
               }
               right++;
           }

        }
        return result;
    }

    public static String minWindow2(String s, String t) {
        String result = "";
        Map<Character, Integer> differMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            differMap.put(t.charAt(i), differMap.getOrDefault(t.charAt(i), 0)+1);
        }
        int left = 0;
        int right = 0;
        Map<Character, Integer> currentMap = new HashMap<>();
        while (right<s.length()){
            if (differMap.containsKey(s.charAt(right))){
                currentMap.put(s.charAt(right), currentMap.getOrDefault(s.charAt(right),0)+1);
            }
            while (check(currentMap, differMap) && left <= right){
                if (result.length()==0 || right-left+1<result.length()){
                    result = s.substring(left, right+1);
                }
                if (differMap.containsKey(s.charAt(left))){
                    currentMap.put(s.charAt(left), currentMap.getOrDefault(s.charAt(left),0)-1);
                }
                left++;
            }
            right++;
        }
        return result;
    }

    private static boolean check(Map<Character, Integer> currentMap, Map<Character, Integer> differMap) {
        for (Character character : differMap.keySet()) {
            if (currentMap.getOrDefault(character, 0)<differMap.get(character)){
                return false;
            }
        }
        return true;
    }

    public static boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            Set<Character> rowSet = new HashSet<>();
            for (int j = 0; j < board[i].length; j++) {
                char c = board[i][j];
                if (c=='.'){
                    continue;
                }
                Set<Character> columnSet = new HashSet<>();
                for (int k = 0; k < i; k++) {
                    if (board[k][j]=='.'){
                        continue;
                    }
                    columnSet.add(board[k][j]);
                }
                Set<Character> areaSet = new HashSet<>();
                int start1 = i - i%3;
                int start2 = j - j%3;
                for (int k = start1; k <= i; k++) {
                    for (int l = start2; l < start2 +3; l++) {
                        if (board[k][l]=='.'){
                            continue;
                        }
                        if (k==i && j==l){
                           break;
                        }
                        areaSet.add(board[k][l]);
                    }
                }
                if (rowSet.contains(c)||columnSet.contains(c)||areaSet.contains(c)){
                    return false;
                }else {
                    rowSet.add(c);
                }
            }
        }
        return true;
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null){
            return result;
        }
        int xLen = matrix.length;
        int yLen = matrix[0].length;
        if (yLen == 0){
            return result;
        }
        int count = xLen*yLen;
        int x = 0;
        int y = 0;
        int times = xLen/2 +(xLen%2 == 0 ? 0 : 1);
        for (int i = 0; i < times; i++) {
            if (x == 0 && y == 0){
                result.add(matrix[x][y]);
            }
            while (y<yLen-i-1 && result.size()<count){
                y++;
                result.add(matrix[x][y]);
            }
            while (x<xLen-i-1 && result.size()<count){
                x++;
                result.add(matrix[x][y]);
            }
            while (y>i && result.size()<count){
                y--;
                result.add(matrix[x][y]);
            }
            while (x>i+1 && result.size()<count){
                x--;
                result.add(matrix[x][y]);
            }
        }
        return result;
    }

    public static void rotate(int[][] matrix) {
        if (matrix != null &&  matrix.length > 0){
            int len = matrix.length;
            int[][] result = new int[len][len];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    result[j][i] = matrix[i][j];
                    System.out.println(matrix[i][j]);
                }
            }
            for (int i = 0; i < result.length; i++) {
                for (int j = 0; j < result[i].length; j++) {
                    matrix[i][result.length-1-j] = result[i][j];
                    System.out.println(matrix[i][j]);
                }
            }
        }
    }

    public static void rotate2(int[][] matrix) {
        if (matrix != null &&  matrix.length > 0){
            int temp = 0;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = i; j < matrix[i].length; j++) {
                    temp = matrix[j][i];
                    matrix[j][i] = matrix[i][j];
                    matrix[i][j] = temp;
                }
            }
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length/2; j++) {
                    temp =  matrix[i][matrix.length-1-j];
                    matrix[i][matrix.length-1-j] = matrix[i][j];
                    matrix[i][j] = temp;
                }
            }
        }
    }

    public void setZeroes(int[][] matrix) {
        int[] row = new int[matrix.length];
        int[] column = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
           for (int j = 0; j < matrix[i].length; j++) {
               if (matrix[i][j] == 0){
                   row[i] = 1;
                   column[j]=1;
               }
           }
       }
       for (int i = 0; i < matrix.length; i++) {
           for (int j = 0; j < matrix[i].length; j++) {
               if (row[i] == 1 || column[j] == 1){
                   matrix[i][j] = 0;
               }
           }
       }
    }

    public static void gameOfLife(int[][] board) {
        int[][] result = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                int count = 0;
                int k = Math.max(i - 1, 0);
                int end1 = Math.min(i + 1, board.length - 1);
                int end2 = Math.min(j + 1, board[i].length - 1);;
                for (; k <= end1; k++) {
                    int l = Math.max(j - 1, 0);
                    for (; l <= end2; l++) {
                        if (board[k][l] == 1 && !(k == i && l == j)){
                            count++;
                        }
                    }
                }
                if (board[i][j] == 1 && (count==2 || count==3)){
                    result[i][j] = 1;
                }else if (board[i][j] == 0 && count == 3){
                    result[i][j] = 1;
                }else{
                    result[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++) {
                board[i][j] = result[i][j];
            }
        }
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> differMap = new HashMap<>();
        for (int i = 0; i < ransomNote.length(); i++) {
            differMap.put(ransomNote.charAt(i),differMap.getOrDefault(ransomNote.charAt(i),0)+1);
        }
        for (int i = 0; i < magazine.length(); i++) {
            if (differMap.containsKey(magazine.charAt(i))){
                differMap.put(magazine.charAt(i),differMap.get(magazine.charAt(i))-1);
                if (differMap.get(magazine.charAt(i)) == 0){
                    differMap.remove(magazine.charAt(i));
                }
            }
        }
        return differMap.size() == 0;
    }

    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null){
            return false;
        }
        if (s.length()!=t.length()){
            return false;
        }
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        int[] hasKey = new int[128];
        int[] hastValue = new int[128];
        for (int i = 0; i < sChar.length; i++) {
            if (hasKey[sChar[i]]!=0 && hasKey[sChar[i]] != tChar[i]){
                return false;
            }else if (hastValue[tChar[i]]!=0 && hastValue[tChar[i]] != sChar[i]){
                return false;
            }
            hasKey[sChar[i]] = tChar[i];
            hastValue[tChar[i]] = sChar[i];
        }
        return true;
    }
    public boolean wordPattern(String pattern, String s) {
        if (pattern == null || s == null){
            return false;
        }
        HashMap<String, Character> wordMap = new HashMap<>();
        HashMap<Character, String> patternMap = new HashMap<>();
        String[] words = s.split(" ");
        if (words.length != pattern.length()){
            return false;
        }
        for (int i = 0; i < words.length; i++) {
            if (wordMap.containsKey(words[i]) && wordMap.get(words[i]) != pattern.charAt(i)){
                return false;
            }
            if (patternMap.containsKey(pattern.charAt(i)) && !patternMap.get(pattern.charAt(i)).equals(words[i])){
                return false;
            }
            wordMap.put(words[i],pattern.charAt(i));
            patternMap.put(pattern.charAt(i),words[i]);
        }
        return true;
    }
    public boolean isAnagram(String s, String t) {
//        Map<Character, Integer> differMap = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            differMap.put(s.charAt(i),differMap.getOrDefault(s.charAt(i),0)+1);
//        }
//        for (int i = 0; i < t.length(); i++) {
//            differMap.put(t.charAt(i),differMap.getOrDefault(t.charAt(i),0)-1);
//            if (differMap.get(t.charAt(i)) == 0){
//                differMap.remove(t.charAt(i));
//            }
//        }
//        return differMap.size() == 0;
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        Arrays.sort(chars);
        Arrays.sort(chart);
        return Arrays.equals(chars,chart);
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> anagramMap = new HashMap<>();
        if (strs == null){
            return result;
        }
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String currentKey = new String(chars);
            if (anagramMap.containsKey(currentKey)) {
                anagramMap.get(currentKey).add(str);
            } else {
                List<String> anagram = new ArrayList<>();
                anagram.add(str);
                anagramMap.put(currentKey, anagram);
            }
        }
        for (Map.Entry<String, List<String>> entry : anagramMap.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }

    public static int[] twoSum4(int[] nums, int target) {
        Map<Integer, Integer> targetMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            targetMap.put(nums[i],i);
            if (targetMap.containsKey(target-nums[i])){
                return new int[]{targetMap.get(target-nums[i]),i};
            }
        }
        return new int[]{0,0};
    }

    public boolean isHappy(int n) {
        if (n<1){
            return false;
        }
        int current = 0;
        if (n>1 && n<10){
            current = n;
        }
        while (n>1){
            int sum = 0;
            while (n>0){
                sum += (n%10)*(n%10);
                n = n/10;
            }
            n = sum;
            if (n>1 && n<10){
                if (n == current){
                    return false;
                }else {
                    current = n;
                }
            }
        }
        return n == 1;
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numMap.containsKey(nums[i])){
                if (i - numMap.get(nums[i]) <= k){
                    return true;
                }else {
                    numMap.put(nums[i],i);
                }
            }
            numMap.put(nums[i],i);
        }
        return false;
    }

    public static int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int len = 0;
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i==0) {
                maxLen = 1;
                len = 1;
            }else{
                if (nums[i]-nums[i-1] == 1){
                    len++;
                }else if (nums[i] > nums[i-1]) {
                    maxLen = Math.max(maxLen,len);
                    len = 1;
                }
            }
        }
        return Math.max(maxLen,len);
    }
    public static int longestConsecutive2(int[] nums) {
        Arrays.sort(nums);
        int len = 0;
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i==0) {
                maxLen = 1;
                len = 1;
            }else{
                if (nums[i]-nums[i-1] == 1){
                    len++;
                }else if (nums[i] > nums[i-1]) {
                    maxLen = Math.max(maxLen,len);
                    len = 1;
                }
            }
        }
        return Math.max(maxLen,len);
    }

    public static List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList();
        if(nums.length == 0){
            return result;
        }
        if (nums.length == 1){
            result.add(nums[0]+"");
        }
        int last = nums[0];
        for(int i=0;i<nums.length;i++){
            if(last == nums[i]){
                continue;
            }
            if(i == nums.length-1){
                if (nums[i]>nums[i-1]+1){
                    result.add(last == nums[i-1] ? nums[i-1]+"" :last+"->"+nums[i-1]);
                    result.add(nums[i]+"");
                }else {
                    result.add(last == nums[i] ? nums[i]+"" :last+"->"+nums[i]);
                }
                continue;
            }
            if(nums[i] > nums[i-1]+1){
                result.add(last == nums[i-1] ? nums[i-1]+"" :last+"->"+nums[i-1]);
                last = nums[i];
            }
        }
        return result;
    }

    public static int[][] merge(int[][] intervals) {
        int [][] result = new int[intervals.length][2];
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        for (int i = 0; i < intervals.length; i++) {
            if (i>0 && result[i-1][1] >= intervals[i][0]){
                result[i][0] = Math.min(result[i-1][0],intervals[i][0]);
                result[i][1] = Math.max(result[i-1][1],intervals[i][1]);
            }else {
                result[i][0] = intervals[i][0];
                result[i][1] = intervals[i][1];
            }
        }
        List<int[]> square = new ArrayList<>();
        for (int i = 0; i < result.length; i++) {
            if (i > 0 && result[i][0] == result[i-1][0]){
                while (i < result.length && result[i][0] == result[i-1][0]){
                    i++;
                }
                i--;
            }
            if (i+1<result.length && result[i][0] == result[i+1][0]){
                continue;
            }
            square.add(new int[]{result[i][0],result[i][1]});
        }
//        int[][] resultSquare = new int[square.size()][2];
//        for (int i = 0; i < square.size(); i++) {
//            resultSquare[i][0] = square.get(i)[0];
//            resultSquare[i][1] = square.get(i)[1];
//        }
//        return resultSquare;
        return square.toArray(new int[square.size()][]);
    }
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ints = new ArrayList<>();
        if (intervals.length == 0){
            ints.add(newInterval);
            return ints.toArray(new int[ints.size()][]);
        }
        if (intervals.length == 1){
            if (newInterval[0] > intervals[0][1]){
                ints.add(intervals[0]);
                ints.add(newInterval);
            }else if (newInterval[1] < intervals[0][0]){
                ints.add(newInterval);
                ints.add(intervals[0]);
            }else {
                int left = Math.min(newInterval[0],intervals[0][0]);
                int right = Math.max(newInterval[1],intervals[0][1]);
                ints.add(new int[]{left,right});
            }
            return ints.toArray(new int[ints.size()][]);
        }
        if (newInterval[0]>intervals[intervals.length-1][1]){
            ints.addAll(Arrays.asList(intervals));
            ints.add(newInterval);
            return ints.toArray(new int[ints.size()][]);
        }else if (newInterval[1]<intervals[0][0]){
            ints.add(newInterval);
            ints.addAll(Arrays.asList(intervals));
            return ints.toArray(new int[ints.size()][]);
        }
        int i = 0;
        int left = 0;
        int leftIndex = 0;
        int right = 0;
        int rightIndex = 0;
        boolean leftFlag = false;
        boolean rightFlag = false;
        while (i<intervals.length){
            if (!leftFlag && newInterval[0] <= intervals[i][1]){
                if (newInterval[0] < intervals[i][0]){
                    leftIndex = i;
                    left = newInterval[0];
                }else {
                    leftIndex = i;
                    left = intervals[i][0];
                }
                leftFlag = true;
            }
            if (!rightFlag && newInterval[1] <= intervals[i][1]){
                if (newInterval[1] < intervals[i][0]){
                    rightIndex = i;
                    right = newInterval[1];
                }else {
                    rightIndex = i;
                    right = intervals[i][1];
                }
                rightFlag = true;
            }
            if (leftFlag && rightFlag){
                break;
            }
            i++;
        }
        if (!rightFlag){
            rightIndex = intervals.length-1;
            right = newInterval[1];
        }
        if (leftIndex == 0 && !rightFlag){
            ints.add(new int[]{left,right});
            return ints.toArray(new int[ints.size()][]);
        }
        for (int j = 0; j < intervals.length; j++) {
            if (j<leftIndex || j > rightIndex){
                ints.add(intervals[j]);
            }else {
                ints.add(new int[]{left,right});
                while (j<rightIndex){
                    j++;
                }
                if (j == rightIndex && intervals[j][0] > right){
                    ints.add(intervals[j]);
                }
            }
        }
        return ints.toArray(new int[ints.size()][]);
    }

    public static int[][] insert2(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }

    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0]){
                    return -1;
                }else if (o1[0] > o2[0]){
                    return 1;
                }
                return 0;
            }
        });
//        List<int[]> square = new ArrayList<>();
//        for (int i = 0; i < points.length; i++) {
//            if (i>0 && square.get(square.size()-1)[1] >= points[i][0]){
//                int left = Math.max(square.get(square.size()-1)[0],points[i][0]);
//                int right = Math.min(square.get(square.size()-1)[1],points[i][1]);
//                square.remove(square.size()-1);
//                square.add(new int[]{left,right});
//            }else {
//                square.add(points[i]);
//            }
//        }
//        return square.size();
        int left = points[0][0];
        int right = points[0][1];
        int count = 0;
        for (int i = 0; i < points.length; i++) {
            if (i>0 && right >= points[i][0]){
                left = Math.max(left,points[i][0]);
                right = Math.min(right,points[i][1]);
            }else {
                left = points[i][0];
                right = points[i][1];
                count++;
            }
        }
        return count;
    }

    public static boolean isValid(String s) {
        boolean flag = false;
        List<Character> characters = new ArrayList<>();
        HashMap<Character, Character> pairs = new HashMap<>();
        pairs.put(')','(');
        pairs.put(']','[');
        pairs.put('}','{');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!pairs.containsKey(c)){
                flag = true;
                characters.add(c);
            }
            if (pairs.containsKey(c)){
                flag = true;
                if (characters.size() == 0){
                    return false;
                }
                if (characters.get(characters.size()-1) != pairs.get(c)){
                    return false;
                }
                characters.remove(characters.size()-1);
            }
        }
        return flag && characters.size() == 0;
    }
    public static boolean isValid2(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Stack<Character> characters = new Stack<>();
        HashMap<Character, Character> pairs = new HashMap<>();
        pairs.put(')','(');
        pairs.put(']','[');
        pairs.put('}','{');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!pairs.containsKey(c)){
                characters.push(c);
            }
            if (pairs.containsKey(c)){
                if (characters.size() == 0){
                    return false;
                }
                if (characters.peek() != pairs.get(c)){
                    return false;
                }
               characters.pop();
            }
        }
        return characters.size() == 0;
    }
    public static String simplifyPath(String path) {
        if (path == null || path.length() == 0){
            return path;
        }
        char[] chars = path.toCharArray();
        String[] str = new String[chars.length+1];
        int i = 0;
        int index = 0;
        StringBuilder sb = new StringBuilder();
        while (i < chars.length){
            if (chars[i] == '/'){
                if (sb.length() != 0){
                    str[index++] = sb.toString();
                    sb.delete(0,sb.length());
                }
                while (i < chars.length && chars[i] == '/'){
                    i++;
                }
                i--;
                str[index++] = sb.append('/').toString();
                sb.delete(0,sb.length());
            }else if (chars[i] == '.'){
                if (sb.length() != 0){
                    str[index++] = sb.toString();
                    sb.delete(0,sb.length());
                }
                while (i < chars.length && chars[i] == '.'){
                    sb.append(chars[i]);
                    i++;
                }
                i--;
                str[index++] = sb.toString();
                sb.delete(0,sb.length());
            }else {
                sb.append(chars[i]);
                if (i == chars.length - 1){
                    str[index++] = sb.toString();
                }
            }
            i++;
        }
        str[index] = "/";
        sb.delete(0,sb.length());
        for (int j = 0; j <= index; j++) {
            if (str[j] != null){
                if (str[j].equals("/")){
                    if (j == 0){
                        sb.append("/");
                    }
                    if (j>=1){
                       if (j>=2 && ".".equals(str[j-1]) && "/".equals(str[j-2])){
                           sb.delete(sb.length()-1,sb.length());
                       }else if (j>=2 && "..".equals(str[j-1]) && "/".equals(str[j-2])){
                           sb.delete(sb.length()-3,sb.length());
                           if (sb.lastIndexOf("/")>-1){
                               sb.delete(sb.lastIndexOf("/"),sb.length());
                           }
                           if (sb.length() == 0){
                               sb.append("/");
                           }
                       }
                       if (sb.length() >1 && !sb.substring(sb.length()-1,sb.length()).equals("/")){
                           sb.append("/");
                       }
                    }
                }else{
                    sb.append(str[j]);
                }
            }
        }
        while (sb.length()> 1 && sb.substring(sb.length()-1,sb.length()).equals("/")){
            sb.delete(sb.length()-1,sb.length());
        }
        return sb.toString();
    }
    public static String simplifyPath2(String path) {
        String[] names = path.split("/");
        Stack<String> stack = new Stack<>();
        for (String name : names) {
            if (name.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!name.isEmpty() && !name.equals(".")) {
                stack.push(name);
            }
        }
        return "/" + String.join("/", stack);
    }
    public int evalRPN(String[] tokens) {
        Stack<String> number = new Stack<>();
        HashSet<Object> calculateSet = new HashSet<>();
        calculateSet.add("+");
        calculateSet.add("-");
        calculateSet.add("*");
        calculateSet.add("/");
        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            if (calculateSet.contains(tokens[i])){
                String pop = number.pop();
                switch (token){
                    case "+":
                        number.push(String.valueOf(Integer.parseInt(number.pop())+Integer.parseInt(pop)));
                        break;
                    case "-":
                        number.push(String.valueOf(Integer.parseInt(number.pop())-Integer.parseInt(pop)));
                        break;
                    case "*":
                        number.push(String.valueOf(Integer.parseInt(number.pop())*Integer.parseInt(pop)));
                        break;
                    case "/":
                       number.push(String.valueOf(Integer.parseInt(number.pop())/Integer.parseInt(pop)));
                }
            }else {
                number.push(tokens[i]);
            }
        }
        return number.size() == 1 ? Integer.parseInt(number.pop()) : 0;
    }
    public static int calculate(String s) {
        Deque<Integer> ops = new LinkedList<>();
        ops.push(1);
        int n = s.length();
        int sign = 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            }else if (c == '+'){
                sign = ops.peek();
            }else if (c == '-'){
                sign = -ops.peek();
            }else if (c == '('){
                ops.push(sign);
            }else if (c == ')'){
                ops.pop();
            }else {
                long num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))){
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                ans += sign * num;
            }
        }
        return ans;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode head = result;
        int nextVal = 0;
        while(l1 != null || l2 != null){
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            result.val = val1 + val2 + nextVal;
            if(result.val >= 10){
                nextVal = result.val-10;
            }
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
            if(l1 != null || l2 != null){
                result.next = new ListNode();
                result = result.next;
            }
        }
        return head;
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode();
        ListNode head = result;
        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                result.next = new ListNode(list2.val);
                result = result.next;
                list2 = list2.next;
            }else {
                result.next = new ListNode(list1.val);
                result = result.next;
                list1 = list1.next;
            }
        }
        result.next = list1 == null ? list2 : list1;
        return head.next;
    }

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[n * 2];
        generateParenthesis(result,chars,0);
        return result;
    }

    private static void generateParenthesis(List<String> result, char[] chars, int pos) {
        if (pos == chars.length){
            if (isValidBracket(new String(chars))){
                result.add(new String(chars));
            }
        }else {
            chars[pos] = '(';
            generateParenthesis(result,chars,pos+1);
            chars[pos] = ')';
            generateParenthesis(result,chars,pos+1);
        }
    }
    private static boolean isValidBracket(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '('){
                count++;
            }else if (c == ')'){
                count--;
                if (count < 0){
                    return false;
                }
            }
        }
        return count == 0;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0){
            return null;
        }
        ListNode current = lists[0];
        for (int i = 1; i < lists.length; i++) {
            current = mergeTwoLists(current, lists[i]);
        }
        return current;
    }

    public static ListNode swapPairs(ListNode head) {
           List<ListNode> listNodes = new ArrayList<>();
           ListNode listNode = new ListNode();
           int count = 0;
           ListNode listNode1 = null;
           ListNode listNode2 = null;
           while (head != null){
               count ++;
               if (count%2 == 0){
                   listNode1 = head;
                   listNodes.add(listNode1);
                   listNodes.add(listNode2);
               }else {
                   listNode2 = head;
               }
               head = head.next;
           }
            if (listNode2 != null){
                listNodes.add(listNode2);
            }
            ListNode current = listNode;
            for (ListNode node : listNodes) {
                if (node!=null){
                    current.next = node;
                    current = current.next;
                }
            }
            current.next = null;
            return listNode.next;
    }

    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        List<ListNode> listNodes = new ArrayList<>();
        ListNode result = new ListNode();
        List<ListNode>  reversList = new ArrayList<>();
        int count = 0;
        while (head != null){
            count ++;
            reversList.add(head);
            if (count%k == 0){
                for (int i = reversList.size()-1; i >= 0; i--) {
                    listNodes.add(reversList.get(i));
                }
                reversList = new ArrayList<>();
            }
            head = head.next;
        }
        if (reversList.size() > 0){
            listNodes.addAll(reversList);
        }
        ListNode current = result;
        for (ListNode node : listNodes) {
            if (node!=null){
                current.next = node;
                current = current.next;
            }
        }
        current.next = null;
        return result.next;
    }
    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        int count = 0;
        int sign = 1;
        if (divisor < 0){
            divisor = -divisor;
            sign = -sign;
        }
        if (dividend < 0){
            dividend = -dividend;
            sign = -sign;
        }
        int result = divisor;
        while(result<=dividend){
            count++;
            result += divisor;
        }
        if (sign == -1){
            count = -count;
        }
        return count;
    }


    public static Node copyRandomList(Node head) {
        Node current = head;
        Node copyNode = new Node(0);
        HashMap<Node,Integer> nodeMap = new HashMap<>();
        List<Node> listNodes = new ArrayList<>();
        int index = 0;
        while (current != null){
            Node node = new Node(current.val);
            listNodes.add(node);
            nodeMap.put(current,index);
            current = current.next;
            index++;
        }
        current = head;
        index = 0;
        while (current != null){
            Node random = current.random;
            if (random != null && nodeMap.containsKey(random)){
                listNodes.get(nodeMap.get(current)).random = listNodes.get(nodeMap.get(random));
            }
            current = current.next;
            index++;
        }
        Node copyHead = copyNode;
        for (int i = 0; i < listNodes.size(); i++) {
            copyHead.next = listNodes.get(i);
            copyHead = copyHead.next;
        }
        return copyNode.next;
    }

    public static Node copyRandomList2(Node head) {
        Node current = head;
        HashMap<Node,Node> nodeMap = new HashMap<>();
        while (current != null){
            Node node = new Node(current.val);
            nodeMap.put(current,node);
            current = current.next;
        }
        current = head;
        while (current != null){
            Node random = current.random;
            Node node = nodeMap.get(current);
            node.random = nodeMap.get(random);
            node.next = nodeMap.get(current.next);
            current = current.next;
        }
        return nodeMap.get(head);
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode current = head;
        left--;
        right--;
        List<ListNode> listNodes = new ArrayList<>();
        while (current!=null){
            listNodes.add(current);
            current = current.next;
        }
        if (left == 0){
            head = listNodes.get(right);
        }
        current = head;
        for (int i = 0; i < listNodes.size(); i++) {
            if (i>=left && i<=right){
                System.out.println(right-i+left);
                current.next = listNodes.get(right-i+left);
            }else {
                current.next = listNodes.get(i);
            }
            current = current.next;
        }
        current.next = null;
        return head;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode current = head;
        List<ListNode> listNodes = new ArrayList<>();
        int count = 0;
        while (current != null){
            listNodes.add(current);
            count++;
            current = current.next;
        }
        ListNode remove = listNodes.remove(count - n);
        if (remove == head){
            head = head.next;
        }else {
            ListNode pre = listNodes.get(count - n - 1);
            pre.next = remove.next;
        }
        return head;
    }

    public static ListNode deleteDuplicates(ListNode head) {
        ListNode ans = new ListNode(0);
        ans.next = head;
        ListNode cur = head;
        while (cur!=null && cur.next!=null){
//            if (cur.val == cur.next.val){
            if (cur.next.val == cur.next.next.val){
                int value = cur.next.val;
                while (cur.next!=null && value == cur.next.val){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return ans.next;
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (k == 0){
            return head;
        }
        List<ListNode> listNodes = new ArrayList<>();
        ListNode cur = head;
        ListNode ans = new ListNode(0);
        ListNode dummy = ans;
        while (cur != null){
            listNodes.add(cur);
            cur = cur.next;
        }
        if (listNodes.size() == 0){
            return head;
        }
        k = k % listNodes.size();
        k = listNodes.size() - k;
        for (int i = k; i < listNodes.size(); i++) {
            ans.next = listNodes.get(i);
            ans = ans.next;
        }
        for (int i = 0; i < k; i++) {
            ans.next = listNodes.get(i);
            ans = ans.next;
        }
        ans.next = null;
        System.out.println(dummy.next.val);
        return dummy.next;
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode cur = head;
        ListNode prefix = new ListNode(0);
        ListNode suffix = new ListNode(0);
        ListNode prefixHead = prefix;
        ListNode suffixHead = suffix;
        while (cur!=null){
            if (cur.val >= x){
                suffix.next = cur;
                suffix = suffix.next;
            }else {
                prefix.next = cur;
                prefix = prefix.next;
            }
            cur = cur.next;
        }
        suffix.next = null;
        prefix.next = suffixHead.next;
        return prefixHead.next;
    }
    static class LRUCache {
        private int capacity;
        private final Map<Integer,Integer> map = new HashMap<>();
        private final List<Integer> history= new ArrayList<>();
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            Integer integer = map.get(key);
            if (integer == null){
                return -1;
            }else {
                for (int i = 0; i < history.size(); i++) {
                    if (history.get(i) == key){
                        history.remove(i);
                        break;
                    }
                }
                history.add(key);
            }
            return integer;
        }

        public void put(int key, int value) {
            if (!map.containsKey(key)){
                if (map.keySet().size()+1>capacity){
                    Integer removeKey = history.get(0);
                    history.remove(removeKey);
                    map.remove(removeKey);
                }
            }else {
                for (int i = 0; i < history.size(); i++) {
                    if (history.get(i) == key){
                        history.remove(i);
                        break;
                    }
                }
            }
            map.put(key,value);
            history.add(key);
        }

    }

}